package leetcode_day._2021._202106._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/8 21:44
 * 最后一块石头的重量
 * 算法：动态规划(01 背包)
 * 求出石头总和，然后除以 2，
 * 就变成 01 背包
 */
public class _08_1049 {

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) sum += stone;
        int[] dp = new int[sum / 2 + 1];
        for (int stone : stones) {
            for (int j = sum / 2; j >= stone; j--) dp[j] = Math.max(dp[j], dp[j - stone] + stone);
        }
        return sum - 2 * dp[sum / 2];
    }

}
